package com.leetcode.problems099;

import com.leetcode.util.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/recover-binary-search-tree/
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    public void recoverTree(TreeNode root) {
        inOrder(root);
    }

    public void inOrder(TreeNode root) {
        TreeNode cur = root;
        TreeNode pre = null;
        TreeNode x = null;
        TreeNode y = null;
        Stack<TreeNode> stack = new Stack<>();
        while(cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if(pre != null && cur.val < pre.val){
                y = cur;
                if (x == null) {
                    x = pre;
                } else {
                    break;
                }
            }
            pre = cur;
            cur = cur.right;
        }
        swap(x,y);
    }

    public void swap(TreeNode x, TreeNode y) {
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }

    public static void main(String[] args) {
        System.out.println();
    }
}